package twobranchsearch.myBST;

import java.util.ArrayDeque;
import java.util.Deque;

public class MyBST<K extends Comparable<K>, V> {

// ============  实例字段    ==========================
	/**
	 * @date 2020/06/08
	 * @author 王光浩
	 * @introduction 一个保存 key-value 的节点
	 */
	private class Node {
		private K key;
		private V value;
		private Node left;
		private Node right;
		private int count;

		public Node(K key, V value, int count) {
			this.key = key;
			this.value = value;
			this.count = count;
		}
	}

	private Node root = null; // 保存二叉树的根节点

// ============  构造方法    ==========================
	/**
	 * 目前仅仅提供无参构造方法
	 */
	public MyBST() {

	}

// ============  实例方法    ==========================

	/**
	 * 根据 key 值来获取对应的 value
	 * @param key
	 * @return 如果集合中没有对应的数据则返回 null，否则返回对应key 的 value
	 */
	public V get(K key) {
		Node node = root;
		while (node != null) {
			if (key.compareTo(node.key) > 0)
				node = node.right;
			else if (key.compareTo(node.key) < 0)
				node = node.left;
			else
				return node.value;
		}
		return null;
	}

	/**
	 * 向该集合中添加键值对
	 * @param key
	 * @param value
	 * @return 如果该 key 已经存在，则更新，并返回 oldValue，否则返回 null
	 */
	public V put(K key, V value) {
		if (root == null) {
			root = new Node(key, value, 1);
		}
		Node temp = root;
		while (key.compareTo(temp.key) != 0) {
			temp.count++; // 该根节点下节点的个数 + 1
			// 如果 key 需要插入到 该根节点的 右子树中
			if (key.compareTo(temp.key) > 0) {
				if (temp.right != null)
					temp = temp.right;
				else {
					temp.right = new Node(key, value, 1);
					return null;
				}
			} else {
				// 该 key-value 需要插入到该 根节点的左子树中
				if (temp.left != null)
					temp = temp.left;
				else {
					temp.left = new Node(key, value, 1);
					return null;
				}
			}
		}
		V oldValue = temp.value;
		temp.value = value;
		return oldValue;
	}

	/**
	 * 将集合中的 value 按照自然顺然输出，
	 */
	public void show() {
		StringBuilder sb = new StringBuilder();
		sb.append("[");
		Deque<Node> stack = new ArrayDeque<Node>();
		if (root == null) {
			System.out.println("[]");
			return;
		}
		stack.push(root);
		while (!stack.isEmpty()) {
			Node node = stack.peek();
			if (node.left != null)
				stack.push(node.left);
			else {
				stack.poll();
				sb.append(node.value + ",");
				while (!stack.isEmpty() && node.right == null) {
					node = stack.poll();
					sb.append(node.value + ",");
				}
				if (node.right != null) {
					stack.push(node.right);
				}
			}
		}
		sb.append("]");
		System.out.println(sb.toString());
	}
}
